﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace FrogEngine
{
	public class Tree<K, T> : ITree<IGeneralTreeNode<K, T>>
	{
		public Tree()
		{
			AllNodes = new List<IGeneralTreeNode<K, T>>();
		}

		public Tree(IGeneralTreeNode<K, T> root)
		{
			this.root = root;
			this.root.Parent = null;
		}

		protected List<IGeneralTreeNode<K, T>> AllNodes { get; private set; }

		private IGeneralTreeNode<K, T> root;
		public IGeneralTreeNode<K, T> Root
		{
			get { return root; }
			set { root = value; }
		}

		protected virtual void AddNode(IGeneralTreeNode<K, T> node)
		{
			AllNodes.Add(node);
		}

		protected virtual void RemoveNode(IGeneralTreeNode<K, T> node)
		{
			AllNodes.Remove(node);
		}

		public int Size
		{
			get { return AllNodes.Count; }
		}

		public int Height()
		{
			return Height(root);
		}

		public int Height(IGeneralTreeNode<K, T> start)
		{
			if (AllNodes.Contains(start))
			{
				if (start.IsExternal)
					return 0;
				else
				{
					int maxHeight = 0;
					foreach (var child in start.Children)
					{
						maxHeight = Math.Max(maxHeight, Height(child));
					}
					return maxHeight + 1;
				}
			}
			else return -1;
		}

		public int Depth(IGeneralTreeNode<K, T> node)
		{
			if (node == root)
				return 0;

			if (AllNodes.Contains(node))
			{
				int count = 0;
				var currentNode = node;
				while (currentNode != root)
				{
					currentNode = currentNode.Parent;
					count++;
				}
				return count;
			}
			else return -1;
		}

		public void PreOrderTraversal<Y>(IGeneralTreeNode<K, T> start, Action<Y> visitAction)
		{
			visitAction((Y)start);
			foreach (var child in start.Children)
				PreOrderTraversal(child, visitAction);
		}

		public void PostOrderTraversal<Y>(IGeneralTreeNode<K, T> start, Action<Y> visitAction)
		{
			foreach (var child in start.Children)
				PostOrderTraversal(child, visitAction);
			visitAction((Y)start);
		}
	}

	public class SearchTree<K, T> : ISearchTree<K, T, IGeneralTreeNode<K, T>>
	{
		public SearchTree()
		{
			AllNodes = new List<IGeneralTreeNode<K, T>>();
		}

		public SearchTree(IGeneralTreeNode<K, T> root)
		{
			this.root = root;
			this.root.Parent = null;
		}

		protected List<IGeneralTreeNode<K, T>> AllNodes { get; private set; }

		public IGeneralTreeNode<K, T> Find(IGeneralTreeNode<K, T> start, K key)
		{
			throw new NotImplementedException();
		}

		public void InsertItem(K key, T value)
		{
			throw new NotImplementedException();
		}

		public void RemoveItem(K key)
		{
			throw new NotImplementedException();
		}

		private IGeneralTreeNode<K, T> root;
		public IGeneralTreeNode<K, T> Root
		{
			get { return root; }
			set { root = value; }
		}

		public int Size
		{
			get { return AllNodes.Count; }
		}

		public int Height()
		{
			return Height(root);
		}

		public int Height(IGeneralTreeNode<K, T> start)
		{
			if (AllNodes.Contains(start))
			{
				if (start.IsExternal)
					return 0;
				else
				{
					int maxHeight = 0;
					foreach (var child in start.Children)
					{
						maxHeight = Math.Max(maxHeight, Height(child));
					}
					return maxHeight + 1;
				}
			}
			else return -1;
		}

		public int Depth(IGeneralTreeNode<K, T> node)
		{
			if (node == root)
				return 0;

			if (AllNodes.Contains(node))
			{
				int count = 0;
				var currentNode = node;
				while (currentNode != root)
				{
					currentNode = currentNode.Parent;
					count++;
				}
				return count;
			}
			else return -1;
		}

		public void PreOrderTraversal<Y>(IGeneralTreeNode<K, T> start, Action<Y> visitAction)
		{
			visitAction((Y)start);
			foreach (var child in start.Children)
				PreOrderTraversal(child, visitAction);
		}

		public void PostOrderTraversal<Y>(IGeneralTreeNode<K, T> start, Action<Y> visitAction)
		{
			foreach (var child in start.Children)
				PostOrderTraversal(child, visitAction);
			visitAction((Y)start);
		}
	}

	public class TreeNode<K, T> : IGeneralTreeNode<K, T>
	{
		public TreeNode()
		{
			children = new List<IGeneralTreeNode<K, T>>();
			visited = false;
		}

		public TreeNode(T value)
		{
			val = value;
			children = new List<IGeneralTreeNode<K, T>>();
			visited = false;
		}

		public TreeNode(T value, IList<IGeneralTreeNode<K, T>> children)
		{
			val = value;
			children = new List<IGeneralTreeNode<K, T>>(children);
			visited = false;
		}

		public TreeNode(T value, IGeneralTreeNode<K, T> parent)
		{
			val = value;
			this.parent = parent;
			children = new List<IGeneralTreeNode<K, T>>();
			visited = false;
		}

		public TreeNode(T value, IGeneralTreeNode<K, T> parent, IList<IGeneralTreeNode<K, T>> children)
		{
			val = value;
			this.parent = parent;
			this.children = new List<IGeneralTreeNode<K, T>>(children);
			visited = false;
		}

		private K key;
		public K Key
		{
			get { return key; }
			set { key = value; }
		}

		private T val;
		public T Value
		{
			get { return val; }
			set { val = value; } 
		}

		private IGeneralTreeNode<K, T> parent;
		public IGeneralTreeNode<K, T> Parent
		{
			get { return parent; }
			set { parent = value; }
		}

		private List<IGeneralTreeNode<K, T>> children;
		public IList<IGeneralTreeNode<K, T>> Children
		{
			get { return children; }
		}

		public bool IsExternal
		{
			get { return children.Count == 0; }
		}

		private bool visited;
		public bool Visited
		{
			get { return visited; }
			set { visited = value; }
		}
	}
}
